//Additive number is a string whose digits can form additive sequence. 
//
// A valid additive sequence should contain at least three numbers. Except for 
//the first two numbers, each subsequent number in the sequence must be the sum of 
//the preceding two. 
//
// Given a string containing only digits '0'-'9', write a function to determine 
//if it's an additive number. 
//
// Note: Numbers in the additive sequence cannot have leading zeros, so 
//sequence 1, 2, 03 or 1, 02, 3 is invalid. 
//
// 
// Example 1: 
//
// 
//Input: "112358"
//Output: true
//Explanation: The digits can form an additive sequence: 1, 1, 2, 3, 5, 8. 
//             1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8
// 
//
// Example 2: 
//
// 
//Input: "199100199"
//Output: true
//Explanation: The additive sequence is: 1, 99, 100, 199. 
//             1 + 99 = 100, 99 + 100 = 199
// 
//
// 
// Constraints: 
//
// 
// num consists only of digits '0'-'9'. 
// 1 <= num.length <= 35 
// 
//
// Follow up: 
//How would you handle overflow for very large input integers? 
// Related Topics 字符串 回溯 👍 184 👎 0

package leetcode.editor.cn;

import org.junit.Assert;

public class P306AdditiveNumber {
    public static void main(String[] args) {
        Solution solution = new P306AdditiveNumber().new Solution();
        Assert.assertEquals(solution.isAdditiveNumber("121474836472147483648"), true);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean isAdditiveNumber(String num) {
            int len = num.length();
            for (int i = 0; i < len - 2; i++) {
                String pre = num.substring(0, i + 1);
                for (int j = i + 1; j < len - 1; j++) {
                    String next = num.substring(i + 1, j+1);
                    String remain = num.substring(j+1);
                    if (isAdditive(pre, next, remain)) {
                        return true;
                    }
                }
            }
            return false;
        }

        public boolean isAdditive(String pre, String next, String remain) {
            int len = remain.length();
            if (len == 0) {
                return true;
            }
            if (isValid(pre, next, remain)) {
                String sum = String.valueOf(Long.parseLong(pre) + Long.parseLong(next));
                if (sum.length() > remain.length()) {
                    return false;
                }
                remain = remain.substring(sum.length());
                return isAdditive(next, sum, remain);
            }
            return false;

        }


        public boolean isValid(String pre, String next, String remain) {
            if (pre.startsWith("0") && pre.length() != 1) {
                return false;
            }
            if (next.startsWith("0") && next.length() != 1) {
                return false;
            }
            if (remain.startsWith("0") && remain.length() != 1) {
                return false;
            }
            Long sum = Long.parseLong(pre) + Long.parseLong(next);
            if (remain.startsWith(String.valueOf(sum))) {
                return true;
            }
            return false;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}